﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace Domain
{
    public class HuffmanTree
    {
        private List<HuffmanTreeNode> Nodes = new List<HuffmanTreeNode>();
        public HuffmanTreeNode Root { get; set; }
        public Dictionary<char, int> Frequencies = new Dictionary<char, int>();

        public void CalculateFrequencies(string source)
        {
            for (int i = 0; i < source.Length; i++)
            {
                if (!Frequencies.ContainsKey(source[i]))
                {
                    Frequencies.Add(source[i], 0);
                }
                Frequencies[source[i]]++;
            }
        }

        public void CreateNodesOfTree()
        {
            foreach (KeyValuePair<char, int> symbol in Frequencies)
            {
                Nodes.Add(new HuffmanTreeNode() { Symbol = symbol.Key, Frequency = symbol.Value });
            }
        }

        public List<HuffmanTreeNode> SortNodes()
        {
            List<HuffmanTreeNode> orderedNodes = Nodes.OrderBy(node => node.Frequency).ToList<HuffmanTreeNode>();
            return orderedNodes;
        }

        public void Build(string source)
        {
            Frequencies.Clear();
            Nodes.Clear();

            CalculateFrequencies(source);
            CreateNodesOfTree();         

            if (Nodes.Count == 1) this.Root = Nodes.FirstOrDefault();
            else
            while (Nodes.Count > 1)
            {
                List<HuffmanTreeNode> orderedNodes = SortNodes();
                
                List<HuffmanTreeNode> taken = orderedNodes.Take(2).ToList<HuffmanTreeNode>();

                HuffmanTreeNode parent = new HuffmanTreeNode()
                {
                    Symbol = '*',
                    Frequency = taken[0].Frequency + taken[1].Frequency,
                    Left = taken[0],
                    Right = taken[1]
                };

                Nodes.Remove(taken[0]);
                Nodes.Remove(taken[1]);
                Nodes.Add(parent);

                this.Root = Nodes.FirstOrDefault();
            }
        }

        public Dictionary<char, BitArray> GetCodeOfAlphabet()
        {
            Dictionary<char, BitArray> CodeOfAlphabet = new Dictionary<char, BitArray>();

            foreach (KeyValuePair<char, int> symbol in Frequencies)
            {
                List<bool> encodedSymbol = Root.GetSymbolCode(symbol.Key, new List<bool>());
                CodeOfAlphabet.Add( symbol.Key, new BitArray(encodedSymbol.ToArray()) );
            }
            return CodeOfAlphabet;
        }        
    }
}
